/*
 * 百度在线网络技术（北京）有限公司拥有本软件版权2021并保留所有权利。
 * Copyright 2021, Baidu.com,Inc 2:Baidu Online Network Technology (Beijing) Co.,Ltd,
 * All rights reserved.
 */

package com.azdebugit.lfu.test;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class LFU<K, V> extends HashMap<K, V> {

    private static final int DEFAULT_MAX_SIZE = 5;
    private int max_size = DEFAULT_MAX_SIZE;
    private Map<K, HitRate> hashMap = new HashMap<>();  //变量类型是Map或HashMap都可以好像

    public static void main(String[] args) {
        LFU<String, String> cache = new LFU<>();
        cache.put("a", "1");
        cache.put("b", "2");
        cache.put("c", "3");
        cache.put("d", "4");
        cache.put("e", "5");
        //此时cache已经满，未定义最大容量，所以默认为5
        System.out.println("当前缓存：" + cache.toString());

        //此时a的命中次数为2
        cache.get("a");
        cache.get("a");

        //删除命中次数最少的b，按照先进先出的意思，找到b为命中次数最少的
        cache.put("f", "6");
        System.out.println("放入f后的缓存：" + cache.toString());

        cache.get("f");   //f命中+1
        cache.get("c");   //c命中+1
        cache.get("d");
        cache.get("e");
        cache.put("g", "7");
        System.out.println("放入g后的缓存：" + cache.toString());
        cache.put("h","8");  //删除命中最少的g
        System.out.println("放入h后的缓存：" + cache.toString());
    }


    //空构造器，使用默认最大值容量
    public LFU() {
        this(DEFAULT_MAX_SIZE);
    }

    //按照传入容量定义容量的构造器
    public LFU(int max_size) {
        super(max_size);
        this.max_size = max_size;
    }

    @Override
    public V get(Object key) {
        //返回指定键映射到的值  第一次get获得hash后对应的数组索引上
        V v = super.get(key);   //根据传入的key调用父级HashMap里的get将其hash()来获取对应的值
        if (v != null) {
            //第二次get取得当前数组索引位置上的HitRate结构上的元素 。并进行修改命中次数
            HitRate hitRate = hashMap.get(key);    //调用Map里的get(),拿到对应的HitRate结构
            hitRate.hitCount += 1;  //让命中次数加一
            System.out.println(key + "被命中" + hitRate.hitCount + "次");
            hitRate.atime = System.nanoTime();   //记录此次时间，纳秒为单位
        }
        //将获取到的值返回
        return v;
    }

    @Override
    public V put(K key, V value) {
        //如果缓存满了，即缓存大小已经到达或超过最大时了
        while (hashMap.size() >= max_size) {
            K k = getLFUAge();    //取出命中最少的键
            hashMap.remove(k);
            this.remove(k);   //从该映射中移除指定键的映射（如果存在）
        }
        //对于数据插入，这里要进行两次Hash去定位数据的存储位置
        V v = super.put(key, value);
        hashMap.put(key, new HitRate(key, 0, System.nanoTime()));
           //增添键值信息
        return v;
    }

    //获取缓存中被命中次数最少的
    private K getLFUAge() {
        //values()返回此映射中包含的值的集合视图
        /***
         * 根据给定集合元素的自然顺序返回该集合的最小元素。*集合中的所有元素都必须实现Comparable接口
         */
        HitRate min = Collections.min(hashMap.values());
        return min.key;
    }

    class HitRate implements Comparable<HitRate> {

        private K key;
        private Integer hitCount;   //记录命中次数
        private Long atime;  //上次命中时间

        public HitRate(K key, Integer hitCount, long atime) {
            this.key = key;
            this.hitCount = hitCount;
            this.atime = atime;
        }

        @Override
        public String toString() {
            return "HitRate{" +
                    "key=" + key +
                    ", hitCount=" + hitCount +
                    ", atime=" + atime +
                    '}';
        }

        @Override
        public int compareTo(HitRate o) {
            int byHitCount = hitCount.compareTo(o.hitCount);   //用命中次数来从小到大排序 相等则=0
            return byHitCount != 0 ? byHitCount : atime.compareTo(atime);   //如果没被命中且要排序就用上次命中时间排序
        }
    }
}
